package com.techyuan.algorithm.sorts;

/**
 * Created by tianjuntao on 2016/12/1.
 */
public class CountingSort implements ISort {
    int max = 0;

    public CountingSort(int max){
        this.max = max;
    }

    public int[] sort(int[] sortingArr) {
        return commonCountingSort(sortingArr, max, new ArrItemNumGetter() {
            public Integer getItem(int[] arr, int index) {
                return arr[index];
            }
        });
    }

    /**
     * 通用版计数排序
     * @param sortingArr
     * @param num
     * @param getter
     * @return
     */
    public int[] commonCountingSort(int[] sortingArr, Integer num, ArrItemNumGetter getter) {
        int[] sortedArr = new int[sortingArr.length];
        int[] countingArr = new int[num];
        //初始化 中间计数数组
        for (int i = 0; i < countingArr.length; i++)
            countingArr[i] = 0;
        //计数
        for (int i = 0; i < sortingArr.length; i++) {
            countingArr[getter.getItem(sortingArr, i)] = countingArr[getter.getItem(sortingArr, i)] + 1;
        }
        //根据计数计算出位置坐标
        for (int i = 1; i < num; i++) {
            countingArr[i] = countingArr[i] + countingArr[i - 1];
        }

        //根据位置开始填写数据
        for (int j = sortingArr.length - 1; j >= 0; j--) {
            sortedArr[countingArr[getter.getItem(sortingArr, j)] - 1] = sortingArr[j];
            countingArr[getter.getItem(sortingArr, j)] = countingArr[getter.getItem(sortingArr, j)] - 1;
        }

        return sortedArr;
    }

    public interface ArrItemNumGetter {
        Integer getItem(int[] arr, int index);
    }
}
